package 左哥算法.ch06二叉树;

import org.junit.Test;

import java.util.*;

/**
 * 栈的思路中：弹出的节点都是中节点，压入的节点中，后压入的是先调用的
 */
public class Ch01遍历 {
    @Test
    public void test01() {
        TreeNode treeNode = new TreeNode();
        treeNode.newTree(3);
        preorder01(treeNode).forEach(System.out::print);    //递归
        System.out.println("");
        preorder02(treeNode).forEach(System.out::print);    //迭代
    }

    /**
     * 递归遍历
     */
    public List<Integer> preorder01(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.add(root.val);
        list.addAll(preorder01(root.left));
        list.addAll(preorder01(root.right));
        return list;
    }

    /**
     * 非递归遍历前序
     * 思路：
     * 使用栈，提前将根节点入栈。重复出栈，以根右左的方式压栈。
     */
    public List<Integer> preorder02(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode father = stack.pop();
            list.add(father.val);
            if (father.right != null) {
                stack.push(father.right);
            }
            if (father.left != null) {
                stack.push(father.left);
            }
        }
        return list;
    }

    /******************/

    @Test
    public void test02() {
        TreeNode treeNode = new TreeNode();
        treeNode.newTree(3);
        inorder01(treeNode).forEach(System.out::print);    //递归
        System.out.println("");
        inorder02(treeNode).forEach(System.out::print);    //迭代
    }

    /**
     * 中序递归
     */
    public List<Integer> inorder01(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.addAll(inorder01(root.left));
        list.add(root.val);
        list.addAll(inorder01(root.right));
        return list;
    }

    /**
     * 非递归中序
     * 思路：
     * 先把所有左节点压入栈，当没有左节点时，此时弹出的就是最左节点(也是中结点)，此时输出该节点
     * 此时该节点左中 都已遍历完成，这时遍历右子树，让当前节点=右节点再进行刚刚的操作
     */
    public List<Integer> inorder02(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        do {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        } while (!stack.isEmpty() || cur != null);
        return list;
    }

    /******后序*******/

    @Test
    public void test03() {
        TreeNode treeNode = new TreeNode();
        treeNode.newTree(3);
        postorder(treeNode).forEach(System.out::print);    //迭代1
        System.out.println();
        postorder2(treeNode).forEach(System.out::print);    //迭代2
    }

    /**
     * 非递归后序
     * 思路：
     * 由先序遍历可知：中右左通过栈可转为中左右，同理中左右则可转为中右左，
     * 而中右左进栈再出栈的结果为左右中
     */
    public List<Integer> postorder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            stack2.push(node);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            list.add(stack2.pop().val);
        }
        return list;
    }

    /**
     * 思路：
     * 准备一个Set集合
     * 先压入中，再压入右和左，
     * 此时弹出的是左子树，但在某种意义上也是中节点，而此时出栈，他是以中节点的方式出栈的（还不知道是否有左右节点）
     * 所以弹出后立即入栈，且计入Set集合中，表示已经出过一次栈。
     * 此时栈中弹出的都是第二次弹出的节点，他们已经遍历过了左右节点。
     *
     * 第一种方式是一种巧解：它通过第一个while将所有元素实现第一次出栈，第二个while将所有元素实现第二次出栈
     * 因为第一次出栈，一定会立马再进去，相当于没出，而第二次出栈时，它已经遍历过左右了，不需要再进去了
     * @param root
     * @return
     */
    public List<Integer> postorder2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Set<TreeNode> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            /*第二次出栈*/
            if (set.contains(cur)) { //可能存在负数，+100是将负数偏移成正数
                list.add(cur.val);
            } else {
                set.add(cur);
                stack.push(cur);
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }

        return list;
    }
}
